#include <bits/stdc++.h>

using namespace std;

// 最长回文子串
// 找到字符串s中最长的回文子串并返回
// 测试链接 : https://leetcode.cn/problems/longest-palindromic-substring/

class Solution 
{
public:
    static const int MAXN = 1001;
    char ss[MAXN << 1];
    int p[MAXN];
    int n, mx, end;

    void manacherss(string& s)
    {
        n = s.size() * 2 + 1;
        for(int i = 0, j = 0; i < n; ++i)
        {
            ss[i] = (i & 1) == 0 ? '#' : s[j++];
        }
    }

    void manacher(string& s)
    {
        manacherss(s);
        mx = end = 0;
        for(int i = 0, c = 0, r = 0, len; i < n; ++i)
        {
            len = r > i ? min(p[2 * c - i], r - i) : 1;
            while(i + len < n && i - len >= 0 && ss[i + len] == ss[i - len])
            {
                ++len;
            }
            if(i + len > r)
            {
                r = i + len;
                c = i;
            }
            if(len > mx)
            {
                mx = len - 1;
                end = (i + len - 1) / 2;
            }
            p[i] = len;
        }
    }

    string longestPalindrome(string s) 
    {
        manacher(s);
        return s.substr(end - mx, mx);
    }
};